package sort

import (
	"fmt"
	"math"
)

type HeapSort struct {
	BaseSort
}

// Sort 堆的建立是基于二叉树的建立，假定元素节点索引为index(此处index的索引是从0开始),并且有左右子节点
// 则 index与左右子节点的关系为：left = 2 * index+1,right = 2 * index + 2
func (self HeapSort) Sort() {
	fmt.Println()
	length := self.Len()
	//建立最大堆
	self.buildMaxHeap(length - 1)

	for i := length - 1; i > 0; i-- {
		self.Swap(0, i)
		length--
		self.heapify(0, length)
	}
}

func (self HeapSort) heapify(index, length int) {
	fmt.Println("堆化前的数组：", self.Array)

	left := 2*index + 1
	right := left + 1
	largest := index

	if left < length && self.Less(largest, left) {
		largest = left
	}
	if right < length && self.Less(largest, right) {
		largest = right
	}
	if largest != index {
		self.Swap(largest, index)
		self.heapify(largest, length)
	}

	fmt.Println("堆化后的数组：", self.Array)
	fmt.Println()
}

func (self HeapSort) buildMaxHeap(length int) {
	i := int(math.Floor(float64(length) / 2)) //堆化时因为只有前半部分才会有子节点所以会向下取整进行堆化
	for ; i >= 0; i-- {
		self.heapify(i, length)
	}
}

func (self HeapSort) Name() string {
	return "堆排序"
}
